410. Split Array Largest Sum
Hard

Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.

Write an algorithm to minimize the largest sum among these m subarrays.

 

Example 1:

Input: nums = [7,2,5,10,8], m = 2
Output: 18
Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

Example 2:

Input: nums = [1,2,3,4,5], m = 2
Output: 9

Example 3:

Input: nums = [1,4,4], m = 3
Output: 4

 

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 106
  • 1 <= m <= min(50, nums.length)
Accepted
125,903
Submissions
266,929
Seen this question in a real interview before?
Companies

Average Rating: 3.63 (128 votes)

Premium

Approach #1 Brute Force [Time Limit Exceeded]

Intuition

Check all possible splitting plans to find the minimum largest value for subarrays.

Algorithm

We can use depth-first search to generate all possible splitting plan. For each element in the array, we can choose to append it to the previous subarray or start a new subarray starting with that element (if the number of subarrays does not exceed m). The sum of the current subarray can be updated at the same time.

Complexity Analysis

  • Time complexity : O(nm)O(n^m). To split n elements into m parts, we can have (n1m1)\binom{n - 1}{m - 1} different solutions. This is equivalent to nm n ^ m.

  • Space complexity : O(n)O(n). The dfs helper function adds a frame to the run-time stack for every element in the list, of which there are nn.


Approach #2 Dynamic Programming [Accepted]

Intuition

The problem satisfies the non-aftereffect property. We can try to use dynamic programming to solve it.

The non-aftereffect property means, once the state of a certain stage is determined, it is not affected by the state in the future. In this problem, if we get the largest subarray sum for splitting nums[0..i] into j parts, this value will not be affected by how we split the remaining part of nums.

To know more about non-aftereffect property, this link may be helpful : http://www.programering.com/a/MDOzUzMwATM.html

Algorithm

Let's define f[i][j] to be the minimum largest subarray sum for splitting nums[0..i] into j parts.

Consider the jth subarray. We can split the array from a smaller index k to i to form it. Thus f[i][j] can be derived from max(f[k][j - 1], nums[k + 1] + ... + nums[i]). For all valid index k, f[i][j] should choose the minimum value of the above formula.

The final answer should be f[n][m], where n is the size of the array.

For corner situations, all the invalid f[i][j] should be assigned with INFINITY, and f[0][0] should be initialized with 0.

Complexity Analysis

  • Time complexity : O(n2m)O(n^2 * m). The total number of states is O(nm)O(n * m). To compute each state f[i][j], we need to go through the whole array to find the optimum k. This requires another O(n)O(n) loop. So the total time complexity is O(n2m)O(n ^ 2 * m).

  • Space complexity : O(nm)O(n * m). The space complexity is equivalent to the number of states, which is O(nm)O(n * m).


Approach #3 Binary Search + Greedy [Accepted]

Intuition

We can easily find a property for the answer:

If we can find a splitting method that ensures the maximum largest subarray sum will not exceed a value x, then we can also find a splitting method that ensures the maximum largest subarray sum will not exceed any value y that is greater than x.

Lets define this property as F(x) for the value x. F(x) is true means we can find a splitting method that ensures the maximum largest subarray sum will not exceed x.

From the discussion above, we can find out that for x ranging from -INFINITY to INFINITY, F(x) will start with false, then from a specific value x0, F(x) will turn to true and stay true forever.

Obviously, the specific value x0 is our answer.

Algorithm

We can use Binary search to find the value x0. Keeping a value mid = (left + right) / 2. If F(mid) is false, then we will search the range [mid + 1, right]; If F(mid) is true, then we will search [left, mid - 1].

For a given x, we can get the answer of F(x) using a greedy approach. Using an accumulator sum to store the sum of the current processing subarray and a counter cnt to count the number of existing subarrays. We will process the elements in the array one by one. For each element num, if sum + num <= x, it means we can add num to the current subarray without exceeding the limit. Otherwise, we need to make a cut here, start a new subarray with the current element num. This leads to an increment in the number of subarrays.

After we have finished the whole process, we need to compare the value cnt to the size limit of subarrays m. If cnt <= m, it means we can find a splitting method that ensures the maximum largest subarray sum will not exceed x. Otherwise, F(x) should be false.

**Complexity Analysis**
  • Time complexity : O(nlog(sumofarray))O(n * log(sum of array)). The binary search costs O(log(sumofarray))O(log(sum of array)), where sum of array is the sum of elements in nums. For each computation of F(x), the time complexity is O(n)O(n) since we only need to go through the whole array.

  • Space complexity : O(1)O(1) space complexity without taking the output list into account, and O(n)O(n) to store the output list.

Report Article Issue

Comments: 66
HawaiianCalm's avatar
Read More

It took me a while to understand what binary search was actually binary searching for. Now that I understand, it's actually pretty simple:

  • Set the search range between min=(largest single value) and max=(sum of all values).
    The min starts there because we're looking for the sum of the largest group in the final set of groups. And no matter what groups you create, the largest value has to be in it, so the largest group can't be smaller than that. (This assumes no negative numbers.)

  • Calculate the midpoint between min and max. This midpoint is the group size we're going to try out to see how well it performs.

  • Split the nums list into groups such that no group has a value larger than the chosen midpoint.
    Note that we may end up with too many or too few groups. That's fine.

  • Compare the number of groups we created against the target m. If we created too many groups, we know the final answer must be between mid+1 and max. That's because we need fewer groups and the way to achieve fewer groups is to increase the allowed maximum sum in each group.

  • On the other hand, if the number of groups is too small, we know the final answer is between min and mid-1 because we need to increase the number of groups which means the target sum is something smaller than the one we used. This is actually also a possible answer assuming m is valid because you can always take any group and split it up to make more groups, so the mid value you targeted is at worst, higher than the real value.

  • On the third hand, if the number of groups is just right, we have a possible answer, so remember that answer. However, we should keep searching just in case there is a better answer. We're ultimately looking for smaller maximum sums, so the potentially better answer is between min and mid-1.

  • Repeat the process until there is nothing else to search. Then use the minimum value we found during the above process.

322
Show 16 replies
Reply
Share
Report
Evercode's avatar
Read More

Approach #2 is actually confusing. The author mix base condition with the transition. Took me some time to figure out. This is more clear

        for (int i=1;i<=n;i++)
            dp[i][1] = sub[i];
        for (int i=1;i<=n;i++){
            for (int j=2;j<=m && j<=i;j++){
                for (int k=1;k<i;k++){
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j-1], sub[i]-sub[k]));
                }
            }
        }

20
Show 4 replies
Reply
Share
Report
snandi1603's avatar
Read More

Such a Pathetic explanation!!!!!

62
Show 2 replies
Reply
Share
Report
JustKeepCodinggg's avatar
Read More

I don't know why leetcode solution explanations are so poor. And let's not even mention the code readability! Leetcode needs to do a better job at filtering and editing these articles.
Here is the same question solved on geek for geeks with great explanation on how the Approach 3 works! - https://www.geeksforgeeks.org/split-the-given-array-into-k-sub-arrays-such-that-maximum-sum-of-all-sub-arrays-is-minimum/

14
Show 3 replies
Reply
Share
Report
wcarvalho's avatar
Read More

Question #2: I also don't understand why mid, a value that is never explicitly constrained to be a sum of the subarrays, will correspond to the sum of the subarrays. Thanks!

12
Show 2 replies
Reply
Share
Report
_LLLLLL_'s avatar
Read More

Python solution for approach 2 throws TLE.

9
Show 3 replies
Reply
Share
Report
mishuman's avatar
Read More

I wish all articles in leetcode was so nicely explained, comprehensible and precise.

19
Show 2 replies
Reply
Share
Report
w238liu's avatar
Read More

Just want to improve the 2nd Approach from two aspects. First, since the minimax sum of k splits only depends on the case of k-1 splits, we may reduce the space complexity from O(m*n) to O(n). Second, the minimax sum of subarrays of nums[:j-1] must be less than or equal to that of nums[:j], so we can apply a binary search instead of the linear search when updating the dp array. The time complexity is thus reduced from O(n^2*m) to O((nlog n) * m). Below shows my python implementation.

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        n = len(nums)
        
        # calculate the cumulative sum of nums[:i], so sum(nums[j:i]) = cumsum[i] - cumsum[j]
        cumsum = [0] * (n + 1)
        for i in range(n):
            cumsum[i + 1] = cumsum[i] + nums[i]
        
        # minimax of one subarray
        dp = list(cumsum)
        
        for k in range(1, m):         # at most m - 1 splits
            for i in range(n, k, -1): # to do k splits, we must have k + 1 numbers, so the minimum i equals k + 1.
                # binary search where dp[j] == sum(nums[j:i]). j ranges from k to i - 1
                left, right = k, i - 1
                while left <= right:
                    mid = (left + right) // 2
                    if dp[mid] >= cumsum[i] - cumsum[mid]:
                        right = mid - 1
                    else:
                        left = mid + 1
                dp[i] = min(max(dp[right], cumsum[i] - cumsum[right]), max(dp[left], cumsum[i] - cumsum[left]))
        
        return dp[-1]

4
Show 2 replies
Reply
Share
Report
kwanmolee's avatar
Read More

To pass all test cases if using DP in python3:

class Solution:
    def splitArray(self, nums, m):
        dp = [[float("inf")] * (len(nums) + 1) for _ in range(m + 1)]
        dp[0][0] = 0
        # accumulative sum
        accu_sum = [0] * (len(nums) + 1)
        for j in range(len(nums)):
            accu_sum[j+1] = accu_sum[j] + nums[j]
        
        for i in range(1, m + 1):
            for j in range(1, len(nums) + 1):
                for k in range(j-1, -1, -1):
                    dp[i][j] = min(dp[i][j], max(dp[i-1][k], accu_sum[j]-accu_sum[k]))
                    ## already found the smallest largest subarray sum, stop
                    if accu_sum[j] - accu_sum[k] > dp[i-1][k]:
                        break
    
        return dp[-1][-1]

4
Reply
Share
Report
jackzhao-mj's avatar
Read More

Here's a Python version of the DP approach:

class Solution(object):
    def splitArray(self, nums, m):
        """
        :type nums: List[int]
        :type m: int
        :rtype: int
        """
        nlen = len(nums)
        dp = [[sys.maxint] * (m + 1) for _ in range(nlen + 1)]
        dp[0][0] = 0
        presum = [0] * (nlen + 1)
        for i, n in enumerate(nums):
            presum[i + 1] = n + presum[i]
        
        for i in range(1, nlen + 1):
            for j in range(1, m + 1):
                for k in range(i):
                    dp[i][j] = min(dp[i][j], max(dp[k][j - 1], presum[i] - presum[k]))
        
        return dp[nlen][m]

3
Show 3 replies
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
05/30/2021 12:15Accepted4 ms7.2 MBcpp
03/25/2021 08:02Accepted0 ms7.2 MBcpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
This list is empty.